О графовой модели для задач рефлектометрии и некоторых алгоритмах их решения.
Часть II. Подход к программной реализации 

Борис Феликсович Мельников, доктор физико-математических наук, профессор, главный научный сотрудник, Центр информационных технологий и систем органов исполнительной власти (Россия, Москва, ул. Пресненский Вал, 19, стр. 1), bormel@mail.ru
Юлия Юрьевна Терентьева, кандидат технических наук, начальник управления анализа и методологии совершенствования информационных  телекоммуникационных систем, Центр информационных технологий и систем органов исполнительной власти (Россия, Москва, ул. Пресненский Вал, 19, стр. 1), terjul@mail.ru

Актуальность и цели. Актуальность рассматриваемой предметной области обусловлена прежде всего необходимостью минимизации стоимости так называемых рефлектометров при имеющемся ограничении на условие тотального мониторинга волоконно-оптических кабелей. Подобные задачи возникают при проектировании и/или модернизации сети связи, причем они особенно важны в тех ситуациях, когда сеть связи имеет очень большую размерность. Целью является исследование возможности применения метода ветвей и границ в нескольких схожих постановках задачи рефлектометрии. Материалы и методы. Применены эвристические алгоритмы искусственного интеллекта и дискретной оптимизации, объединенные в единый программный пакет, а также статистические методы анализа алгоритмов. Результаты. Результатами являются закономерности, полученные при применении жадной эвристики и вариантов метода ветвей и границ при решении задач рефлектометрии. Выводы. Были предложены алгоритмы, описывающие улучшение метода ветвей и границ с помощью подключения к нему различных вспомогательных эвристик. Однако полученное временнóе улучшение среднего времени работы этого алгоритма в рассмотренной нами прикладной задаче – по сравнению с жадным алгоритмом – очень невелико, и это позволяет сделать предварительные выводы о том, что в задачах рефлектометрии достаточным является применение простейших жадных алгоритмов.

Ключевые слова

эвристические алгоритмы, задачи дискретной оптимизации, модели теории графов, жадный алгоритм, метод ветвей и границ

 Скачать статью в формате PDF

Для цитирования:

Мельников Б. Ф., Терентьева Ю. Ю. О графовой модели для задач рефлектометрии и некоторых алгоритмах их решения. Часть II. Подход к программной реализации // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2022. № 3. С. 32–42. doi:10.21685/2072-3040-2022-3-4